import java.util.ArrayList;
import java.util.List;

/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/7/2 20:36
 */
// 求根节点到叶子节点数字之和
    // https://leetcode.cn/problems/sum-root-to-leaf-numbers/
    // dfs
public class Solution129 {
    int result = 0;
    List<Integer> path = new ArrayList<>();
    public int sumNumbers(TreeNode root) {
        if (root == null) return result;
        path.add(root.val);
        backtrack(root);
        return result;
    }

    private void backtrack(TreeNode root) {
        if (root.left == null && root.right == null) {
            result += pathToInt(path);
            return;
        }
        if (root.left != null) {
            path.add(root.left.val);
            backtrack(root.left);
            path.remove(path.size() - 1);
        }
        if (root.right != null) {
            path.add(root.right.val);
            backtrack(root.right);
            path.remove(path.size() - 1);
        }
        return;
    }

    private int pathToInt(List<Integer> path) {
        int sum = 0;
        for(Integer num : path) {
            sum = sum * 10 + num;
        }
        return sum;
    }
}
